ff1588d761d55f48f61a52249e1dcc24

<!DOCTYPE html>

<title>Iterative Dichotomiser 3</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Iterative Dichotomiser 3</span></h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr"><p><b>Iterative Dichotomiser 3</b> (<b>ID3</b>) ist ein <a href="Algorithmus" title="Algorithmus">Algorithmus</a>, der zur Entscheidungsfindung dient. Er wird bei <a href="Entscheidungsbaum" title="Entscheidungsbaum">Entscheidungsbäumen</a> eingesetzt. Der australische Forscher J. Ross Quinlan publizierte diesen Algorithmus erstmals im Jahr <a href="1986" title="1986">1986</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> ID3 war in seinen ersten Jahren sehr einflussreich. Er findet auch heute noch in einigen Produkten Verwendung. ID3 gilt als Vorgänger des <a href="C4.5" title="C4.5">C4.5</a>-Algorithmus.

</p><p>ID3 wird verwendet, wenn bei großer Datenmenge viele verschiedene Attribute von Bedeutung sind und deshalb ein Entscheidungsbaum ohne große Berechnungen generiert werden soll. Somit entstehen meist einfache Entscheidungsbäume. Es kann aber nicht garantiert werden, dass keine besseren Bäume möglich wären.

</p><p>Die Basisstruktur von ID3 ist <a href="Iteration" title="Iteration">iterativ</a>. Es werden zu jedem noch nicht benutzten Attribut <a href="Entropie_(Informationstheorie)" title="Entropie (Informationstheorie)">Entropien</a> bezüglich der Trainingsmenge berechnet. Das Attribut mit dem höchsten Informationsgewinn (englisch: information gain) bzw. der kleinsten Entropie, wird gewählt und daraus ein neuer Baum-Knoten generiert. Das Verfahren terminiert, wenn alle Trainingsinstanzen klassifiziert wurden, d. h. wenn jedem Blattknoten eine Klassifikation zugeordnet ist.

</p>

<div class="mw-heading mw-heading2"><h2 id="Algorithmus">Algorithmus</h2></div>

<p>Wenn alle Elemente aus <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"></span> (Daten) zu einer Klasse gehören

</p>

<dl><dd>Dann

<dl><dd>// Erzeuge ein Blatt //

<dl><dd>Konstruiere ein Blatt mit der Klasse als Bezeichner</dd></dl></dd></dl></dd></dl>

<dl><dd>Sonst

<dl><dd>// Erzeuge rekursiv einen Teilbaum //

<dl><dd>Wähle das „informativste“ Merkmal <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"></span></dd>

<dd>Beginn: Für_alle vorkommenden Werte von Merkmal <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"></span>

<dl><dd>Konstruiere alle Teilbäume rekursiv mit den entsprechenden Teilmengen als Daten</dd></dl></dd>

<dd>Konstruiere einen Baumknoten mit Bezeichner <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e87000dd6142b81d041896a30fe58f0c3acb2158.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.129ex; height:2.009ex;" alt="{\displaystyle x_{i}}" loading="lazy"></span> und hänge alle erzeugten Teilbäume an</dd></dl></dd></dl></dd>

<dd>Ende Sonst</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Auswahl_der_Attribute_(Merkmale)"><span id="Auswahl_der_Attribute_.28Merkmale.29"></span>Auswahl der Attribute (Merkmale)</h2></div>

<p>Für die Bildung der Teilbäume wird jeweils entsprechend der <a href="Informationstheorie" title="Informationstheorie">Informationstheorie</a> das informativste Attribut ausgewählt.

</p><p>Sei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> die Menge der Trainingsbeispiele mit ihrer jeweiligen Klassifizierung, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\in A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\in A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a97387981adb5d65f74518e20b6785a284d7abd5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.814ex; height:2.176ex;" alt="{\displaystyle a\in A}" loading="lazy"></span> das zu prüfende Attribut aus der Menge der verfügbaren Attribute, <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle V(a)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle V(a)}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9bcc24423086a74188ec73473af3cc9a74722bab.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.826ex; height:2.843ex;" alt="{\displaystyle V(a)}" loading="lazy"></span> die Menge der möglichen Attributwerte von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S_{v}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S_{v}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92feed1a3e76a5a2bf8233f7376f6ddb932807f3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.455ex; height:2.509ex;" alt="{\displaystyle S_{v}}" loading="lazy"></span> die Untermenge von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span>, für die das Attribut <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> den Wert <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle v}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle v}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e07b00e7fc0847fbd16391c778d65bc25c452597.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.128ex; height:1.676ex;" alt="{\displaystyle v}" loading="lazy"></span> annimmt. Der Informationsgewinn, der durch Auswahl des Attributs <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span> erzielt wird, errechnet sich dann als Differenz der Entropie von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> und der erwarteten/durchschnittlichen Entropie von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle S}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle S}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4611d85173cd3b508e67077d4a1252c9c05abca2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.499ex; height:2.176ex;" alt="{\displaystyle S}" loading="lazy"></span> bei Fixierung von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"></span>:

</p><p><span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle G(S,a)=\operatorname {Entropie} (S)-\sum _{v\in V(a)}{\dfrac {|S_{v}|}{|S|}}\operatorname {Entropie} (S_{v})}">

<mi>Entropie</mi>

</mrow>

</munder>

<mfrac>

<mrow>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

<mrow>

</mrow>

</mrow>

</mfrac>

</mstyle>

</mrow>

<mi>Entropie</mi>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(S,a)=\operatorname {Entropie} (S)-\sum _{v\in V(a)}{\dfrac {|S_{v}|}{|S|}}\operatorname {Entropie} (S_{v})}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0b7beb84ca9d603f0641de43b7f404168f6b16a5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.505ex; width:49.227ex; height:7.343ex;" alt="{\displaystyle G(S,a)=\operatorname {Entropie} (S)-\sum _{v\in V(a)}{\dfrac {|S_{v}|}{|S|}}\operatorname {Entropie} (S_{v})}" loading="lazy"></span>.

</p><p>Schließlich wählt man ein Attribut mit dem größtmöglichen Gewinn aus der Menge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \lbrace a_{next}\in A|G(S,a_{next})=\max _{a\in A}(G(S,a))\rbrace }">

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</munder>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \lbrace a_{next}\in A|G(S,a_{next})=\max _{a\in A}(G(S,a))\rbrace }</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7e1def5b52cf56fefaf0c88ae9468620fd90fab3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.171ex; width:39.854ex; height:4.176ex;" alt="{\displaystyle \lbrace a_{next}\in A|G(S,a_{next})=\max _{a\in A}(G(S,a))\rbrace }" loading="lazy"></span> als das nächste Attribut.

</p><p>Diese Wahl führt zur Bevorzugung von Attributen mit vielen Wahlmöglichkeiten und damit zu einem breiten Baum. Um dem entgegenzuwirken, kann eine Normalisierung über die Anzahl der Wahlmöglichkeiten durchgeführt werden.

</p>

<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>

<li><a href="CHAID" title="CHAID">CHAID</a></li>

<li><a href="Top-Down_Induction_of_Decision_Trees" title="Top-Down Induction of Decision Trees">TDIDT</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://ipub.com/id3-with-data-tree/">Implementierung des ID3 Algorithmus in R</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">J. Ross Quinlan: <cite style="font-style:italic">Induction of Decision Trees</cite>. In: <cite style="font-style:italic">Machine Learning</cite>. <span style="white-space:nowrap">Band<span style="display:inline-block;width:.2em"> </span>1</span>, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, März 1986, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>81–106</span>, <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<span class="uri-handle" style="white-space:nowrap"><a rel="nofollow" class="external text" href="https://doi.org/10.1007/BF00116251">10.1007/BF00116251</a></span>.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Iterative+Dichotomiser+3&rft.atitle=Induction+of+Decision+Trees&rft.au=J.+Ross+Quinlan&rft.date=1986-03&rft.doi=10.1007%2FBF00116251&rft.genre=journal&rft.issue=1&rft.jtitle=Machine+Learning&rft.pages=81-106&rft.volume=1" style="display:none"> </span></span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2024-09-14" href="https://de.wikipedia.org/wiki/?title=Iterative_Dichotomiser_3&oldid=248599326">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>